#include "HuffmanTree.h"
using namespace std;

//按照降序排列
void shellSort(int* num, int numsize)
{
	assert(num);

	int gap = numsize;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = gap; i < numsize; i++)
		{
			int end = i - gap;
			int tmp = num[i];
			while (end >= 0)
			{
				if (num[end] < tmp)
				{
					num[end + gap] = num[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			
			num[end + gap] = tmp;
		}
	}
	/*while (gap > 0)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; j++)
		{
			for (int i = gap + j; i < numsize; i += gap)
			{
				int end = i - gap;
				int tmp = num[i];
				while (end > 0)
				{
					if (num[end] < tmp)
					{
						num[end + gap] = num[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}

				num[end + gap] = tmp;
			}
		}
	}*/
}
HTNode* CreateTreeNode(int val)
{
	HTNode* ret = (HTNode*)malloc(sizeof(HTNode));
	if (NULL == ret)
	{
		perror("malloc fail");
	}
	else
	{
		ret->val = val;
		ret->left = ret->right = ret->parent = NULL;
	}

	return ret;
}

void HTreeInit(HTree* hTree, int n)
{
	assert(hTree);

	hTree->nodeList = (HTNode**)malloc(sizeof(HTNode*) * (2 * n - 1));
	if (NULL == hTree->nodeList)
	{
		perror("malloc fail");
	}
	else
	{
		hTree->size = 0;
	}
}

void CreateHTreeNode(HTree* hTree, int* num, int n)
{
	assert(hTree);

	HTreeInit(hTree, n);
	for (int i = 0; i < n; i++)
	{
		hTree->nodeList[i] = CreateTreeNode(num[i]);
	}
	hTree->size = n;
}

HTNode* CreateHTree(HTree* hTree)
{
	assert(hTree);

	HTNode* root = NULL;
	int i = hTree->size - 1;
	while (i > 0)
	{
		if (i - 1 >= 0)
		{
			int tmp = hTree->nodeList[i]->val + hTree->nodeList[i - 1]->val;
			HTNode* node = CreateTreeNode(tmp);
			node->left = hTree->nodeList[i];
			node->right = hTree->nodeList[i - 1];
			hTree->nodeList[i]->parent = hTree->nodeList[i - 1]->parent = node;
			hTree->nodeList[hTree->size] = node;
			(hTree->size)++;
			i--;
			HTNodeSort(hTree->nodeList, hTree->size);
		}
	}
	root = hTree->nodeList[0];

	return root;
}

void HTNodeSort(HTNode** nodeList, int size)
{
	assert(nodeList);

	int end = size - 2;
	HTNode* tmp = nodeList[size - 1];
	while (end >= 0)
	{
		if (nodeList[end]->val < tmp->val)
		{
			nodeList[end + 1] = nodeList[end];
			end--;
		}
		else
		{
			break;
		}
	}

	nodeList[end + 1] = tmp;
}

void HTreeDestroy(HTree* hTree)
{
	assert(hTree);
	for (int i = 0; i < hTree->size; i++)
		free(hTree->nodeList[i]);
	free(hTree->nodeList);
	hTree->size = 0;
}

int CalculateHTree(HTNode* root, int height)
{
	int ret = 0;
	if (root != NULL)
	{
		if (root->left == NULL && root->right == NULL)
			ret = root->val * height;
		else
			ret = CalculateHTree(root->left, height + 1) + CalculateHTree(root->right, height + 1);
	}

	return ret;
}